#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int i = 1;
        int j = 0;
        int n = nums.size();
        while (i < n)
        {
            if (nums[i] != nums[j])
            {
                nums[++j] = nums[i];
            }
            i++;
        }
        return j + 1;
    }
};


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        vector<int> v(m + n);
        int i = 0;
        int j = 0;
        int z = 0;
        while (i < m && j < n)
        {
            if (nums1[i] <= nums2[j])
            {
                v[z++] = nums1[i++];
            }
            else
            {
                v[z++] = nums2[j++];
            }
        }
        while (i < m)
        {
            v[z++] = nums1[i++];
        }
        while (j < n)
        {
            v[z++] = nums2[j++];
        }
        for (int i = 0; i < m + n; i++)
            nums1[i] = v[i];
    }
};

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val)
    {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur)
        {
            if (cur->val == val)
            {
                if (cur == head)
                {
                    cur = cur->next;
                    delete head;
                    head = cur;
                }
                else
                {
                    prev->next = cur->next;
                    delete cur;
                    cur = prev->next;
                }
            }
            else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        ListNode* prev = nullptr;
        ListNode* cur = head;

        while (cur)
        {
            ListNode* next = cur->next;

            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newhead;
    }
};

class Solution {
public:
    ListNode* middleNode(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};